package cn.zifangsky.array.questions;

import org.apache.commons.lang3.StringUtils;
import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 指定长度的数组的子集的排列情况算法
 *
 * <p>给定一个不重复的数组，求指定长度的数组子集的排列情况。</p>
 *
 * <ol>
 *     <li>输入：arr = [a], len = 1；结果：[a]</li>
 *     <li>输入：arr = [a, b], len = 2；结果：[ab, ba]</li>
 *     <li>输入：arr = [a, b, c], len = 3；结果：[abc, acb, bca, bac, cab, cba]</li>
 *     <li>输入：arr = [a, b, c], len = 2；结果：[ab, ac, bc, ba, ca, cb]</li>
 * </ol>
 *
 * @author zifangsky
 * @date 2021/7/8
 * @since 1.0.0
 */
public class Problem_010_ArrayArrangement {

    /**
     * 测试代码
     */
    @Test
    public void testMethods(){
        List<String> keySet1 = getArrayArrangement(Arrays.asList("a"), 1);
        List<String> keySet2 = getArrayArrangement(Arrays.asList("a", "b"), 2);
        List<String> keySet3 = getArrayArrangement(Arrays.asList("a", "b", "c"), 3);
        List<String> keySet4 = getArrayArrangement(Arrays.asList("a", "b", "c"), 2);

        System.out.println(StringUtils.join(keySet1, ","));
        System.out.println(StringUtils.join(keySet2, ","));
        System.out.println(StringUtils.join(keySet3, ","));
        System.out.println(StringUtils.join(keySet4, ","));
    }

    /**
     * 获取数组的排列情况
     */
    private List<String> getArrayArrangement(List<String> arr, int len){
        List<String> keySet = new LinkedList<>();
        loopGet(keySet, arr, new LinkedList<>(), len, 0, 0);
        return keySet;
    }

    /**
     * 指定长度的数组的子集的排列情况
     * @author zifangsky
     * @date 2021/7/8
     * @since 1.0.0
     * @param keySet 最终排列情况的结果集
     * @param original 原始数组
     * @param oneResult 执行过程中的某一个排列结果
     * @param len 子集的长度
     * @param level 当前级别，用于递归求得数组子集的每一个位置的元素
     * @param startIdx 当前这个 level 从哪个 Idx 开始遍历
     */
    private void loopGet(List<String> keySet, List<String> original, LinkedList<String> oneResult, int len, int level, int startIdx) {
        int size = original.size();
        //每一级都循环取数，最多取 size - level 次
        for (int i = (startIdx % size), num = 0; num < (size - level); i = ((i + 1) % size)) {
            String item = original.get(i);
            //循环取数的时候不能跟前面已经取的数重复，否则尝试取后面一个数
            if(oneResult.contains(item)){
                continue;
            }
            oneResult.add(item);
            num++;

            if(oneResult.size() == len) {
                keySet.add(StringUtils.join(oneResult, ""));
            }else {
                loopGet(keySet, original, oneResult, len, (level + 1), (i + 1));
            }
            //得到结果后最后一个数要出栈，返回上一级后当前的最后一个数也要出栈
            oneResult.pollLast();
        }
    }
}
